package top.hudk.sort;

import java.util.HashMap;
import java.util.Map;

/**
 * 淘汰最久没有使用过的缓存数据算法
 */
public class LRUCache {

    /**
     * 初始容量
     */
    private int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    /**
     * 哈希表，用于在O（1）的时间内找到目标元素
     */
    private Map<Integer, Node> map = new HashMap<>();

    /**
     * 链表尾部元素
     */
    private Node<Integer, Integer> tail;

    /**
     * 链表头部元素
     */
    private Node<Integer, Integer> head;

    /**
     * 添加新的键值对元素
     *
     * @param key
     * @param value
     * @return
     */
    public Integer put(int key, int value) {
        //若新增的内容，缓存中没有，且当下容量已经达到最大容量，则将头部元素删除（头部元素是最久没有访问过的元素）
        if (!map.containsKey(key) && map.size() == capacity) {
            deleteHead();
        }
        //若第一次新增元素
        if (map.size() == 0) {
            this.head = new Node<>(key, value, null, null);
            this.tail = this.head;
            map.put(key, this.head);
            //System.out.println(toString());
            return null;
        }
        //如果缓存中已经存在该键的内容，则将其在链表中的位置移到链表的尾部，并更新其内容。
        if (map.containsKey(key)) {
            setLastAndUpdate(key, value);
        } else {
            //如果缓存没有该键的内容，则直接将其追加到尾部
            linkLast(key, value);
        }
        //System.out.println(toString());
        return null;
    }

    /**
     * 从缓存中获取指定键对应的值内容
     *
     * @param key
     * @return
     */
    public Integer get(int key) {
        //如果该键存在缓存中，则将该键值元素在链表中的位置，移到链表尾部，并返回其值内容
        if (map.containsKey(key)) {
            setLast(key);
            //System.out.println(toString());
            return this.tail.item;
        } else {
            //如果缓存中没有找到该键对应的数据，则返回-1
            //System.out.println(toString());
            return -1;
        }
    }

    /**
     * 将新的元素，放到链表尾部，并加入到哈希表中
     *
     * @param key
     * @param value
     */
    private void linkLast(Integer key, Integer value) {
        Node<Integer, Integer> tail = this.tail;
        Node<Integer, Integer> newNode = new Node<>(key, value, null, this.tail);
        this.tail = newNode;
        if (tail == null) {
            this.head = newNode;
        } else {
            tail.next = newNode;
        }
        map.put(key, newNode);
    }

    /**
     * 删除链表头部元素
     */
    private void deleteHead() {
        if (this.head != null) {
            map.remove(this.head.kay);
            this.head.kay = null;
            this.head.item = null;
            Node next = this.head.next;
            if (next != null) {
                this.head.next.prev = null;
                this.head.next = null;
                this.head = next;
            }

        }
    }


    /**
     * 将集合中已有的指定元素，放到尾部，并更新它的内容
     *
     * @param key
     * @param value
     */
    private int setLastAndUpdate(Integer key, Integer value) {
        setLast(key);
        return this.tail.item = value;
    }

    /**
     * 将集合中已有的指定元素，放到尾部，并更新它的内容
     *
     * @param key
     */
    private int setLast(Integer key) {
        Node<Integer, Integer> node = map.get(key);
        if (this.head == this.tail || node == this.tail) {
            return this.tail.item;
        }
        if (node.next != null && node.prev != null) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
        if (node == this.head) {
            node.next.prev = null;
            this.head = node.next;
        }
        this.tail.next = node;
        node.prev = tail;
        node.next = null;
        this.tail = node;
        return this.tail.item;
    }

    /**
     * 链表元素
     *
     * @param <K>
     * @param <V>
     */
    private static class Node<K, V> {
        K kay;
        V item;
        LRUCache.Node<K, V> next;
        LRUCache.Node<K, V> prev;

        Node(K kay, V element, LRUCache.Node<K, V> next, LRUCache.Node<K, V> prev) {
            this.kay = kay;
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
}